//
// Created by pangy on 2025/5/11.
//

#include "LinkList.h"

/*--------------------------------内存操作-----------------------------------*/
/**
 * 分配结点空间,创建结点p, 值为e.
 * @param p 指向结点的指针
 * @param e 结点值
 * @return OK/ERROR
 */
Status MakeNode(Link* p, ElemType e) {
    if (p == NULL) {
        return ERROR;
    }

    // 申请空间
    *p = (Link) malloc(sizeof(LNode));

    if (*p == NULL) {
        exit(OVERFLOW);
    }

    (*p)->data = e;
    (*p)->next = NULL;

    return OK;
}

/**
 * 释放结点空间
 * @param p 指向结点的指针
 */
void FreeNode(Link* p) {
    if (p == NULL || *p == NULL) {
        return;
    }

    free(*p);

    *p = NULL;
}


/*---------------------------------链表常规操作------------------------*/
/**
 * 构造一个空的链表 L
 * 成功返回OK,失败返回ERROR
*/
Status InitList(LinkList* L) {
    Link p;
    if (L == NULL) {
        return ERROR;
    }

    p = (Link) malloc(sizeof(LNode));
    if (p == NULL) {
        exit(OVERFLOW);
    }

    // 头结点/尾结点都指向刚分配的结点
    L->head = L->tail = p;
    L->len = 0;

    return OK;
}

/**
 * 销毁线性表
 * 成功返回OK, 失败返回ERROR
 * */
Status DestroyList(LinkList* L) {
    // 线性表不能为空
    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    // 清空结点
    ClearList(L);

    // 释放头结点空间
    free(L->head);
    L->head = L->tail = NULL;

    return OK;
}

/**
 * 清空线性表, 释放原链表的节点空间
 * 只保留头结点
 * 成功返回OK,失败返回ERROR
*/
Status ClearList(LinkList* L) {
    Link p, q;

    if (L == NULL || L->head == NULL || L->len <= 0) {
        return ERROR;
    }

    // p指向第一个节点
    p = L->head->next;

    while (p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }

    L->head->next = NULL;
    L->tail = L->head;
    L->len = 0;

    return OK;
}

/**
 * 线性表判空
 * 空表返回TRUE, 否则返回FALSE
 * */
Boolean ListEmpty(LinkList L) {
    return L.len == 0;
}

/**
 * 线性表长度
 * 返回线性表长度, 空表返回0
 * */
int ListLength(LinkList L) {
    return L.len;
}

/**
 * 返回链表中第一个满足compare条件的结点
 * @param L 链表
 * @param e 数据元素值
 * @param Compare 比较函数
 * @return 结点
 */
Position LocateElem(LinkList L, ElemType e, Status (Compare)(ElemType, ElemType)) {
    Position p;

    // 空表返回NULL
    if (L.len <= 0) {
        return NULL;
    }

    // p指向第一个元素
    p = L.head->next;

    // 循环直到表尾或满足Compare函数
    while (p != NULL && !Compare(p->data, e)) {
        p = p->next;
    }

    return p;
}

/**
 * 在指定位置插入数据元素
 * @param L 线性表
 * @param i 指定位置
 * @param e 插入数据元素
 * @return OK/ERROR
 */
Status ListInsert(LinkList* L, int i, ElemType e) {
    Link h, s;
    Status result;

    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    // 校验i
    if (i < 1 || i > L->len + 1) {
        return ERROR;
    }

    // 找到第i-1个元素, 赋给h
    result = LocatePos(*L, i - 1, &h);
    if (result == ERROR) {
        return ERROR;
    }

    // 分配新结点
    result = MakeNode(&s, e);

    s->next = h->next;
    h->next = s;

    return OK;
}

/**
 * 删除指定位置的数据元素
 * @param L 线性表
 * @param i 位置
 * @param e 删除的数据元素
 * @return OK/ERROR
 */
Status ListDelete(LinkList* L, int i, ElemType* e) {
    Link h, s;

    // 校验链表存在
    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    // 校验i范围
    if (i < 1 || i > L->len) {
        return ERROR;
    }

    // 查找第i-1个元素
    if (LocatePos(*L, i - 1, &h) == ERROR) {
        return ERROR;
    }

    s = h->next;
    h->next = s->next;

    *e = s->data;
    // 释放删除的结点空间
    FreeNode(&s);

    return OK;
}

/**
 * 线性表数据元素依次操作
 * @param L 线性表
 * @param Visit 操作函数
 */
void ListTraverse(LinkList L, void (*visit)(ElemType)) {
    Link p;
    if (L.len <= 0) {
        return;
    }

    p = L.head->next;
    while (p != NULL) {
        visit(p->data);
        p = p->next;
    }
}



/*-----------------------------链表扩展操作--------------------------------------*/

/**
 * head为链表头结点,将s指向结点插入到第一个结点之前
 * @param head 头结点
 * @param s 待插入结点
 * @return OK/ERROR
 */
Status InsertFirst(LinkList *L, Link s) {
    // 校验列表L存在
    if (L == NULL || L->head == NULL || s == NULL) {
        return ERROR;
    }

    s->next = L->head->next;
    L->head->next = s;
    L->len++;

    return OK;
}

/**
 * head为链表头结点, 删除第一个结点并赋给q
 * @param head
 * @param q
 * @return OK/ERROR
 */
Status DeleteFirst(LinkList *L, Link* q) {
    Link p;
    // 校验链表L存在
    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    // 空表
    if (L->len == 0) {
        return ERROR;
    }

    *q = L->head->next;

    L->head->next = (*q)->next;
    (*q)->next = NULL;
    L->len--;

    return OK;
}

/**
 * 将结点s追加到链表L末尾
 * @param L 链表
 * @param s 结点
 * @return ok/ERROR
 */
Status Append(LinkList* L, Link s) {
    int count;

    // 校验链表存在
    if (L == NULL || L->head == NULL || s == NULL) {
        return ERROR;
    }

    L->tail->next = s;

    count = 0;
    // 循环计算s指向结点串的长度
    while (s != NULL) {
        L->tail = s;
        s = s->next;
        count++;
    }

    L->len += count;

    return OK;
}

/**
 * 删除末尾结点
 * @param L
 * @param q
 * @return
 */
Status Remove(LinkList* L, Link* q) {
    Link  p;

    // 校验链表存在
    if (L == NULL || L->head == NULL) {
        return ERROR;
    }

    *q = L->tail;

    // 空表
    if (L->len == 0) {
        *q = NULL;
        return OK;
    }

    p = L->head;

    // 遍历到表尾, 此时p指向倒数第二个元素
    while (p->next != L->tail) {
        p = p->next;
    }

    p->next = NULL;
    L->tail = p;
    L->len--;

    return OK;
}

/**
 * 插入元素到指定结点之前
 * @param L 链表
 * @param p 指定结点
 * @param s 插入结点
 * @return
 */
Status InsertBefore(LinkList* L, Link* p, Link s) {
    Link h;

    // 校验链表L存在
    if (L == NULL || L->head == NULL || p == NULL || s == NULL) {
        return ERROR;
    }

    // p 指向头结点
    if (*p == L->head) {
        return ERROR;
    }

    h = L->head;
    while (h->next != NULL && h->next != *p) {
        h = h->next;
    }

    // 遍历整个链表L,未找到p指向的结点
    if (h->next == NULL) {
        return ERROR;
    }

    s->next = h->next;
    h->next = s;
    L->len++;

    *p = s;

    return OK;
}

/**
 * 插入结点到指定结点之后
 * @param L
 * @param p
 * @param s
 * @return
 */
Status InsertAfter(LinkList* L, Link* p, Link s) {
    Link r;

    // 验证链表L存在
    if (L == NULL || L->head == NULL || p == NULL || s == NULL) {
        return ERROR;
    }

    r = L->head;
    while (r != NULL && r != *p) {
        r = r->next;
    }

    // 未发现p指向的结点
    if (r == NULL) {
        return ERROR;
    }

    s->next = r->next;
    r->next = s;
    L->len++;

    *p = s;

    return OK;
}

/**
 * 更新结点数据域
 * @param p 结点
 * @param e 数据
 * @return OK/ERROR
 */
Status SetCurElem(Link p, ElemType e) {
    // 判断p是否存在
    if (p == NULL) {
        return ERROR;
    }

    p->data = e;
    return OK;
}

/**
 * 获取结点数据域
 * @param p
 * @param e
 * @return
 */
ElemType GetCurElem(Link p) {
    if (p == NULL) {
        return INT_MIN;
    }

    return p->data;
}

/**
 * 返回链表头结点
 * @param L
 * @return
 */
Position GetHead(LinkList L) {
    return L.head;
}

/**
 * 返回链表尾结点
 * @param L
 * @return
 */
Position GetLast(LinkList L) {
    return L.tail;
}

/**
 * 返回指定结点的前驱
 * @param L
 * @param p
 * @return
 */
Position PriorPos(LinkList L, Link p) {
    Link pre;

    if (L.head == NULL) {
        return NULL;
    }

    if (p == NULL) {
        return NULL;
    }
    pre = L.head;

    // 第一个结点无前驱
    if (p->next == L.head) {
        return NULL;
    }

    while (pre != NULL && pre->next != p) {
        pre = pre->next;
    }

    return pre;
}

/**
 * 返回指定结点的后继
 * @param L
 * @param p
 * @return
 */
Position NextPos(LinkList L, Link p) {
    if (L.head == NULL || p == NULL) {
        return NULL;
    }

    return p->next;
}

/**
 * 返回链表指定索引的结点
 * @param L 链表
 * @param i 索引
 * @param p 结点
 * @return OK/ERROR
 */
Status LocatePos(LinkList L, int i, Link* p) {
    Link r;
    int j;

    // i = 1 表示头结点
    if (i < 0 || i > L.len) {
        return ERROR;
    }

    // 验证头结点存在
    if (L.head == NULL) {
        return ERROR;
    }

    // i = 0 时, 返回头结点
    if (i == 0) {
        (*p) = L.head;
        return OK;
    }

    r = L.head;
    j = 0;

    // 遍历到表尾或指定位置i
    while (r != NULL && j < i) {
        r = r->next;
        j++;
    }

    // 链表与长度不一致?
    if (r == NULL) {
        return ERROR;
    }

    (*p) = r;

    return OK;
}
